/*
Date:20210607 21:58PM
key:这题就是按数组顺序每次选择+或者-，千万注意+完要-，-完更要+。
    由于是一直往右走所以不需要用集合
    在回溯函数里写累计值dfs(nums, target,re+nums[i],count,i+1);,而不是加完再放re进去
    动态规划
    目标范围-Max,Max。然后j上一个偏移量才行
*/
class Solution 
{
public:
    // void dfs(const vector<int>& nums, const int &target,int re,int&count,int i)
    // {
    //     if(i==nums.size())
    //     {
    //         if(re==target)
    //         {
    //             count++;
                
    //         }
    //         return;
    //     }

    //     {
            
    //         dfs(nums, target,re+nums[i],count,i+1);
            

    //         dfs(nums, target,re-nums[i],count,i+1);

    //     }
        
    // }
    int dp[21][0xff7];
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        int re=0,count=0;
        //dfs(nums,target,re,count,0);
        memset(dp,0,sizeof(dp));
        const int n=nums.size();
        const int m=target;
        //最远极限
        int Max=0;
        for(int&g:nums)
        {
            Max+=abs(g);
        }
        //先填第一层，考虑前0个
        for(int j=0;j<=Max*2;j++)
        {
            dp[0][j]=0;
        }
        dp[0][Max]=1;
        //从考虑第一个物品开始，逐行填写
        for(int i=1;i<n+1;i++)
        {
            for(int j=-Max;j<=Max;j++)
            {
                if(j+Max-nums[i-1]>-1&&j+Max-nums[i-1]<=Max*2)
                {
                    dp[i][j+Max]=dp[i-1][j+Max-nums[i-1]];
                }
                if(j+Max+nums[i-1]>-1&&j+Max+nums[i-1]<=Max*2)
                {
                    dp[i][j+Max]+=dp[i-1][j+Max+nums[i-1]];
                }
                //cout<<dp[i][j]<<"\t";
            }
            //cout<<"\n";
        }
        return dp[n][m+Max];
    }
    
};